We propose a novel adaptive approximation approach for test-time resource-constrained prediction motivated by Mobile, IoT, health, security and other applications, where constraints in the form of computation, communication, latency and feature acquisition costs arise. We learn an adaptive low-cost system by training a gating and prediction model that limits utilization of a high-cost model to hard input instances and gates easy-to-handle input instances to a low-cost model. Our method is based on adaptively approximating the high-cost model in regions where low-cost models suffice for making highly accurate predictions. We pose an empirical loss minimization problem with cost constraints to jointly train gating and prediction models. On a number of benchmark datasets our method outperforms state-of-the-art achieving higher accuracy for the same cost.

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/

The idea of taking into account feature costs when pruning tree ensembles is original to the best of my knowledge. The main originality of the proposed approach is the fact that it adopts a bottom-up post-pruning strategy, while most existing approaches are top-down, acting during tree growing. While the authors present this feature as an advantage of their method, actually, I'm not convinced that adopting a bottom-up strategy is a good idea for addressing this problem. Since the algorithm indeed can not modify the existing tree structure (it can only prune it), it should be less efficient in terms of feature cost reduction than top-down methods that can have a direct impact on the features selected at tree nodes. For example, let us assume that two very important features in the dataset carry on the exact same information about the output (i.e, they are redundant).

Thus, the paper is similar to the work of Xu et al., 2012. The main differences are the fact that the feature and evaluation costs are input-specific, the evaluation cost depends on the number of tree splits, their optimization approach is different (based on the Taylor expansion around T_{k-1}, as described in the XGBoost paper), and they use best-first growth to grow the trees to a maximum number of splits (instead of a max depth). The authors point out that their setup works either in the case where feature cost dominates or evaluation cost dominates and they show experimental results for these settings.

Neural Information Processing Systems http://nips.cc/

Many applications require learning classifiers or regressors that are both accurate and cheap to evaluate. Prediction cost can be drastically reduced if the learned predictor is constructed such that on the majority of the inputs, it uses cheap features and fast evaluations. The main challenge is to do so with little loss in accuracy. In this work we propose a budget-aware strategy based on deep boosted regression trees. In contrast to previous approaches to learning with cost penalties, our method can grow very deep trees that on average are nonetheless cheap to compute. We evaluate our method on a number of datasets and find that it outperforms the current state of the art by a large margin. Our algorithm is easy to implement and its learning time is comparable to that of the original gradient boosting.

This paper presents a novel technique for incorporating user input when learning and inferring In high stakes decision settings such as credit scoring, processing user preferences. When trying to provide users bail applications, or making hiring decisions, applicants of black-box machine learning models with actionable often seek recourse to correct unfavourable predicted recourse, we often wish to incorporate outcomes for the future. In these scenarios, since there their personal preferences about the ease of modifying can be multiple possible recourses for each individual, feasibility each individual feature. These recourse considerations, user preferences, and heuristics to finding algorithms usually require an exhaustive minimize the size of the proposed modifications are used to set of tuples associating each feature to its cost guide the search for appropriate recourses (Poyiadzi et al., of modification. Since it is hard to obtain such 2020; Pawelczyk et al., 2020; Joshi et al., 2019). Recourse costs by directly surveying humans, in this paper, search algorithms thus return the best possible recourse we propose the use of the Bradley-Terry model based on these considerations by performing a search over to automatically infer feature-wise costs using the feature-space of the model.